package gererg;

/**
 * @author leon(liangzou0318@gmail.com)
 * @date 2012-11-22
 * @filaname CoinsChange.java
 */
public class CoinsChange {
     public static void makechange(int[] values,int money,int valueKinds,int[] coinsUsed){
    	 coinsUsed[0]=0;
    	 for(int cents=60;cents<=money;cents++){
    		 int minCoins=cents;
    		 for (int kind = 1; kind <valueKinds; kind++) {               
                 // 若当前面值的硬币小于当前的cents则分解问题并查表  
                 if (values[kind] <= cents) {  
                     int temp = coinsUsed[cents - values[kind]] + 1;
                     System.out.println(temp);
                     if (temp < minCoins) {  
                         minCoins = temp;                        
                     }                      
                 }            
             }  
    		 coinsUsed[cents] = minCoins;  
             System.out.println("面值为 " + (cents) + " 的最小硬币数 : " 
                     + coinsUsed[cents]);
    	 }
     }
	public static void main(String[] args) {
		int money=63;
		int[] coinvalue=new int[]{25,21,10,5,1};
		int[] coinused=new int[money+1];
		makechange(coinvalue,money,coinvalue.length,coinused);

	}

}
